package cn.cxq.learning.tree;

import java.util.ArrayList;

/**
 * 牛客题霸-研发最爱考
 *
 * 字典树的实现
 *  算法知识视频讲解
 * 中等  通过率：54.22%  时间限制：2秒  空间限制：256M
 * 知识点
 * 高级结构
 * 字符串
 * 题目
 * 题解(3)
 * 讨论(21)
 * 排行
 * 描述
 * 字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。void insert(String word)：添加word，可重复添加；void delete(String word)：删除word，如果word添加过多次，仅删除一次；boolean search(String word)：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量。现在给定一个m，表示有m次操作，每次操作都为以上四种操作之一。每次操作会给定一个整数op和一个字符串word，op代表一个操作码，如果op为1，则代表添加word，op为2则代表删除word，op为3则代表查询word是否在字典树中，op为4代表返回以word为前缀的单词数量（数据保证不会删除不存在的word）。
 *
 * 对于每次操作，如果op为3时，如果word在字典树中，请输出“YES”，否则输出“NO”；如果op为4时，请输出返回以word为前缀的单词数量，其它情况不输出。
 * 示例1
 * 输入：
 * [["1","qwer"],["1","qwe"],["3","qwer"],["4","q"],["2","qwer"],["3","qwer"],["4","q"]]
 * 复制
 * 返回值：
 * ["YES","2","NO","1"]
 * 复制
 * 备注：
 * m \leq 10^5m≤10
 * 5
 *
 * |word| \leq 20∣word∣≤20
 * 关联企业
 * 关联职位
 */
public class Trie {
    Trie[] child; // 记录子节点，新建26个代表26个小写字母，如果为空即代表字典树中没有出现该字母
    int count; // 记录根到此节点为前缀的字符串的个数
    boolean isEnd; // 记录该节点是否为一个单词的最后一个字母

    public String[] trieU (String[][] operators) {
        // write code here
        Trie trie = new Trie();

        ArrayList<String> res = new ArrayList<>();

        for (String[] operator : operators) {
            switch (operator[0]) {
                case "1" :
                    trie.insert(operator[1]);
                    break;
                case "2" :
                    trie.delete(operator[1]);
                    break;
                case "3" :
                    res.add(trie.search(operator[1]) ? "YES" : "NO");
                    break;
                case "4" :
                    res.add(String.valueOf(trie.prefixNumber(operator[1])));
            }
        }
        return res.toArray(new String[res.size()]);
    }

    public Trie() {
        child = new Trie[26];
        count = 0;
        isEnd = false;
    }

    public void insert(String word) {

        Trie cur = this;

        for (char c : word.toCharArray()) {
            if (cur.child[c - 'a'] == null) {
                cur.child[c - 'a'] = new Trie();
            }

            cur = cur.child[c - 'a'];
            cur.count++;
        }

        cur.isEnd = true;
    }

    public void delete(String word) {

        Trie cur = this;

        for (char c : word.toCharArray()) {
            if(cur.child[c-'a'] == null){
                return;
            }
            if (cur.child[c - 'a'].count == 1) {
                cur.child[c - 'a'] = null;
                return;
            }
            cur = cur.child[c - 'a'];
            cur.count--;
        }
    }

    public boolean search(String word) {

        Trie cur = this;

        for (char c : word.toCharArray()) {
            if (cur.child[c - 'a'] == null) {
                return false;
            }
            cur = cur.child[c - 'a'];
        }

        return cur.isEnd;
    }

    public int prefixNumber(String pre) {

        Trie cur = this;

        for (char c : pre.toCharArray()) {
            if (cur.child[c - 'a'] == null) {
                return 0;
            }
            cur = cur.child[c - 'a'];
        }

        return cur.count;
    }
}
